<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>
<body>
    <script>
        // 1. 三数之和
        // 时间复杂度：O(nlogn)是排序的，内层循环是O(n^2)，总的时间复杂度是O(n^2)
        // 空间复杂度：O(1)
        var threeSum = function(nums) {
            // 排序
            nums.sort((a, b) => a - b)
            let n = nums.length
            let ans = []
            for (let i = 0; i < n - 3; i++) {
                // 去重优化
                if (i > 0 && nums[i] === nums[i - 1]) continue
                // 优化边界
                if (nums[i] + nums[i + 1] + nums[i + 2] > 0) break
                if (nums[i] + nums[n - 1] + nums[n - 2] < 0) continue

                let j = i + 1
                let k = n - 1
                while (j < k) {
                    if (nums[i] + nums[j] + nums[k] < 0) {
                        j++
                    } else if (nums[i] + nums[j] + nums[k] > 0) {
                        k--
                    } else {
                        // 找到一个目标序列
                        ans.push([nums[i], nums[j], nums[k]])
                        // 去重优化 如下两种写法是错误写法
                        // for (j++; j < k; j++) {
                        //     if (nums[j] === nums[j - 1]) {
                        //         continue
                        //     }
                        // }
                        // for (k--; j < k; k--) {
                        //     if (nums[k] === nums[k + 1]) {
                        //         continue
                        //     }
                        // }
                        // 这样才能去重，无论如何j和k都要往中间靠一下先
                        for (j++; j < k && nums[j] === nums[j - 1];j++) continue
                        for (k--; j < k && nums[k] === nums[k + 1];k--) continue
                    }
                }
            }
            return ans
        };
        // console.log(threeSum([0, 0, 0]));
        console.log(threeSum([-1, 0, 1, 2, -1, -4]));
        // [-1,0,1,2,-1,-4]
        // console.log(threeSum([-5, 1, 3, 7, 4, 2]));
        // console.log(threeSum([1]));
    </script>
</body>
</html>